import sys


def main():
    # 总钱数, 商品数量
    n, m = map(int, input().split())
    n //= 10
    # 价格,满意度=重要度*价格,主件-附件 []
    things_main = []
    things_append = []

    for i in range(m):
        # 价格, 重要度, 主件/附件
        thing = list(map(int, input().split()))
        thing[0] //= 10
        thing[1] *= thing[0]
        if thing[2] == 0:
            thing.append(i + 1)
            thing.append([])
            things_main.append(thing)
        else:
            things_append.append(thing)

    for t_append in things_append:
        for t_main in things_main:
            if t_append[2] == t_main[3]:
                t_main[-1].append(t_append)
                break

    dp = [0 for i in range(n + 1)]

    for i in range(0, len(things_main)):
        t_main = things_main[i]
        for j in range(n, t_main[0] - 1, -1):
            dp_j = dp[j - t_main[0]] + t_main[1]

            if len(t_main[-1]) == 1:
                t_append0 = t_main[-1][0]

                if j >= t_main[0] + t_append0[0]:
                    dp_j = max(dp_j, dp[j - t_main[0] - t_append0[0]] + t_main[1] + t_append0[1])

            if len(t_main[-1]) == 2:
                t_append0 = t_main[-1][0]
                t_append1 = t_main[-1][1]

                if j >= t_main[0] + t_append0[0]:
                    dp_j = max(dp_j, dp[j - t_main[0] - t_append0[0]] + t_main[1] + t_append0[1])
                if j >= t_main[0] + t_append1[0]:
                    dp_j = max(dp_j, dp[j - t_main[0] - t_append1[0]] + t_main[1] + t_append1[1])
                if j >= t_main[0] + t_append0[0] + t_append1[0]:
                    dp_j = max(dp_j, dp[j - t_main[0] - t_append0[0] - t_append1[0]] + t_main[1] + t_append0[1] + t_append1[1])

            dp[j] = max(dp[j], dp_j)

    print(dp[-1] * 10)


if __name__ == '__main__':
    with open('../input.txt', "r") as fr:
        sys.stdin = fr
        while True:
            try:
                main()
            except EOFError:
                break
